#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
#include <map>
#include <set>
#include <string>
using namespace std;

template<class MapIt, class OutputIt>
void copy_first(MapIt first, MapIt end, OutputIt it)
{
    for (; first != end; (void)++first, (void)++it)
        *it = first->first;

}

template<class MapIt, class SetIt, class OutputIt>
void set_difference_with_map_and_set( MapIt first1, MapIt last1, SetIt first2, SetIt last2, OutputIt d_first )
{
    while (first1 != last1)
    {
        if (first2 == last2)
        {
            copy_first(first1, last1, d_first);
            return;
        }
        const auto &first_val = first1 -> first;
        if (first_val < *first2)
        {
            *d_first++ = first_val;
            ++first1;
        }
        else
        {
            if (! (*first2 < first_val))
                ++first1;
            ++first2;
        }
    }
}


template<class SetIt, class MapIt, class OutputIt>
void set_difference_with_set_and_map( SetIt first1, SetIt last1, MapIt first2, MapIt last2, OutputIt d_first )
{
    while (first1 != last1)
    {
        if (first2 == last2)
        {
            std::copy(first1, last1, d_first);
            return;
        }
        const auto &first_val = first2 -> first;
        if (*first1 < first_val)
            *d_first++ = *first1++;
        else
        {
            if (! (first_val < *first1))
                ++first1;
            ++first2;
        }
    }
}

auto print_seq = [](const auto& v, string end = "", string type_ = "")
{
    cout << type_;
    cout << "{ ";
    for (auto i : v) cout << i << ' ';
    cout << "} " << end;
};

auto print_map = [](const auto& v, string end = "", string type_ = "")
{
    cout << type_;
    cout << "{ ";
    for (auto i : v) cout << i.first << ' ';
    cout << "} " << end;
};


int main()
{
    map <int, int> mp;
    set <int> st, tmp_mp;
    vector <int> res;
    mp.insert({ 1, 1 });
    mp.insert({ 2, 1 });
    print_map(mp, "\n", "map = ");
    st.insert(3);
    st.insert(2);
    print_seq(st, "\n", "set = ");
    set_difference_with_map_and_set(mp.begin(), mp.end(), st.begin(), st.end(), back_inserter(res));
    print_seq(res, "\n", "res = ");
    return 0;
}